package Top101K;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @Author quan
 * @Description 缺失的第一个正整数
 * @Date 2023/11/20 13:56
 */
public class BM53_MinNumberDisappeared {
    public static void main(String[] args) {
        int[] arr = {3,2,1};
        System.out.println(minNumberDisappeared(arr));
    }

    /**
     * 给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数
     * @param nums  [-2,3,4,1,5] ——> 2
     * @return  [4,5,6,8,9] ——> 1
     */
    public static int minNumberDisappeared (int[] nums) {
        // write code here
        //1-获取数组的最大值max_num
        //2-将所有的元素都存储到哈希表中
        HashSet<Integer> set = new HashSet<>();
        int max_num = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > max_num){
                max_num = nums[i];
            }
            set.add(nums[i]);
        }
        //3-从1开始遍历到最大值，如果这个值在哈希表中存在，就继续遍历
        for (int i = 1; i < max_num+1; i++) {
            //4-一旦该值在哈希表中不存在，说明该元素就是最小的正整数
            if(!set.contains(i)){
                return i;
            }
        }
        //5-注意：{3,2，1}这种情况，如果哈希表中不存在，那最小值就是最大值加1，就是3+1
        return max_num+1;
    }
}
